#ifndef __JOESPHUS__
#define __JOESPHUS__
#define NON_DATASTRUCT 1
#define DATASTRUCT 0

#if DATASTRUCT
class Node{
public:
	Node():data(false),next(NULL){}
	bool data;
	Node *next;
	int num;
};

void Joesphus(int len, int start, int num){

	//initial
	Node *head,*p;
	head = new Node();
	head->num = 1;
	p = head;

	int cnt = 1;
	for(;;){
		if(cnt == len) break;
		p->next = new Node();
		p = p->next;
		++cnt;
		p->num = cnt;
	}
	p->next = head;

	//start, find the 1st one
	p = head; cnt = 0;
	for(;;){
		if(++cnt == start) break;
		p = p->next;
	}

	cnt = 0;
	int n = 0;
	for(;;){
		if(cnt == (len-1)) break;
		if(p->data == false){
			n++;
		}
		if(n == num){
			n = 0;
			p->data = true;
			cnt++;
		}
		p = p->next;
	}
	//show the answer
	p = head;
	for(;;){
		if(p->data == false){
			printf("%d",p->num);
			break;
		}
		p = p->next;
	}
	
	//clean
	p = head;
	Node *p1;
	for(int i = 0; i< len; ++i){
		p1 = p->next;
		delete p;
		p = p1;
	}

}
#endif

#if NON_DATASTRUCT
void Josephus(int n,int start,int to){
	int * arr = new int[n+1];
	for(int i = 1; i < n+1; ++i){
		arr[i] = 1;
	}
	int index = start;
	int len = n;

	//process n-1 times
	for(int i = 0; i < n-1; ++i){
		int cnt = 0;		
		for(;;){
			if(cnt == to) break;
			if(index > n) index = 1;
			if(arr[index++] == 1){
				++cnt;
			}
		}
		arr[index-1] = 0;	
	}

	for(int i =1 ; i<n+1;++i){
		if(arr[i]!=0){
			printf("%d",i);
		}
	}
	delete [] arr;

}
#endif

#endif